1. Field of the Invention
The present invention relates to a method of and a device for labeling each pixel in an image. In particular, the invention relates to a labeling method and a labeling circuit, in which a temporary label is added or assigned to each pixel by scanning a local image region in an image, a concatenation relationship between the temporary labels is stored, and a final label is added to each pixel based on the concatenation relationship. More particularly, the invention relates to a labeling method and a labeling device in which raster scan of a local image region in a binary image is carried out, a provisional label is added to a run detected on a lower row in the local image region, and a temporary label for each pixel in this run is determined when the run is detected again on an upper row in the local image region thereafter. The invention also relates to a labeling method and a labeling device for processing an image bearing a temporary label, in which a common label is successively added to the concatenated regions according to a concatenation state of temporary labels.
2. Description of the Related Art
As one of image processing systems, there is a measuring system using a vision recognition system, in which shapes or forms of recognition objects, i.e., objects to be recognized, are distinguished from each other, and processing such as measurement of areas of the distinguished objects and/or calculation of a number of recognition objects contained in a screen is performed.
FIG. 73 shows an example of a structure of a conventional measuring system using a vision recognition system. In FIG. 73, the measuring system includes a visual sensor 990 formed of, e.g., an ITV (industrial television) camera for producing image information from a recognition object, an A/D converter 991 for converting analog image signals sent from the visual sensor 990 into digital image signals, a binary-encoding circuit 992 for effecting threshold processing on the digital image signals sent from the A/D converter 991 with a predetermined threshold value to produce binary image data, and a labeling circuit 993 for labeling each pixel in the binary image sent from the binary-encoding circuit 992.
The labeling circuit 993 detects concatenated regions in an image data series applied thereto, and adds peculiar labels to the concatenated regions for identifying objects in the image. A measuring circuit 994 identifies the objects in the image in accordance with the image labeled by the labeling circuit 993, and carries out the processing such as measurement of the areas or calculation of the number thereof. Operations of the visual sensor 990 and labeling circuit 993 will be briefly described below with reference to FIG. 74.
The visual sensor 990 supplies an analog image signal produced by scanning the screen in the raster scan manner. The analog image signal supplied from the visual sensor 990 is converted by the A/D converter 991 into the digital image signal as shown at (a) in FIG. 74. At (a) in FIG. 74, there are shown regions A, B and C of relatively large values of image data.
The binary-encoding circuit 992 effects the threshold processing on the output of the A/D converter 991 to produce regions A', B' and C' of logic "1" corresponding to the regions A, B and C at (a) in FIG. 74, respectively, as shown at (b) in FIG. 74.
Remaining image regions are set to logic "0". The labeling circuit 993 distinguishes the concatenation regions A', B' and C' in the binary images shown at (b) in FIG. 74, and adds peculiar labels to respective concatenation regions. In an example shown at (c) in FIG. 74, the regions A', B' and C' bear labels 1, 2 and 3, respectively.
Different labels mean different regions including different objects, i.e., non-concatenated regions in the image. The measuring circuit 994 extracts the regions of the same labels in accordance with the labels, and carries out the processing such as calculation of the area and/or number of the object.
FIG. 75 schematically shows labeling steps by the labeling circuit. As shown at (a) in FIG. 75, a binary mask 24 extracts local image regions from an input binary image. Labeling is effected on a unit, of each local image region thus extracted. The binary mask 24 utilized in this example cuts out the local image region consisting of pixels arranged in two rows of three columns. In FIG. 76, the binary mask 24 scans binary image data P(i-1, j+1), P(i-1, j) and P(i-1, j-1) corresponding to three pixel positions (i-1, j+1), (i-1, j) and (i-1, j-1) with an upper row 24b. A lower row 24a of the binary mask 24 extracts image data P(i, j+1), P(i, j) and P(i, j-1) corresponding to three pixel positions (i, j+1), (i, j) and (i, j-1) adjacent to the pixels extracted by the upper row 24b of the binary mask. The binary mask 24 scans the binary image in a raster scan manner.
The local image regions in the binary image which are extracted from the input binary image by the binary mask 24 are processed to extract pixel regions (runs) each including concatenated pixels, and the labels of the reference pixels are determined using adjacent pixel data in the binary mask and adjacent pixel labels which have been processed. As a result, as shown at (b) in FIG. 75, a temporary label image, in which each pixel bears a temporary label, is produced. The process has been conducted by extracting the local image regions with the binary mask, so that different labels may be assigned to the same concatenated components. Therefore, if there exist confluent points of labels, which are indicated by circles at (b) in FIG. 75, relationship representing the fact that the concatenated components adjacent to the confluent points have concatenated labels is stored in a label correlation table shown at (c) in FIG. 75. At (c) in FIG. 75, there is shown a state in which such a relationship is stored that the labels 2 and 3 are connected and form the same concatenated component, labels 3 and 4 are elements forming the same concatenated component, and labels 5 and 6 are elements forming the same concatenated component.
After scanning all the binary image and labeling each pixel, each label of the temporary label image is converted into the final label to produce a final label image in accordance with the label connection relationship stored in the label correlation table (see (d) in FIG. 75). The process in which the label correlation table is analyzed to produce the final label image from the temporary label image is generally called a unification process.
For the above process, the labeling circuit is formed of a hardware so as to perform the labeling of each pixel in real time as far as possible.
FIG. 77 shows a structure of a conventional labeling circuit for labeling the binary image. The structure of the labeling circuit shown in FIG. 77 is disclosed, for example, in Japanese Patent Laying-Open No. 2-48778 (1990).
Referring to FIG. 77, the labeling circuit includes a mask forming portion 1 which receives a binary image data I1 and produces a binary image data corresponding to pixels in two rows and three columns shown in FIG. 76. The mask forming portion 1 includes three shift registers 11a, 11b and 11c arranged in tandem for receiving the input binary image data I1, a 1-bit line buffer 10 receiving the input binary image data I1, and three shift registers 11d, 11e and 11f arranged in tandem for receiving the output of line buffer 10. The 1-bit line buffer 10 delays the input binary image data I1 by an amount corresponding to one row (i.e., one scan line in the raster scan). Each of the shift registers 11a-11f delays the received binary image data by an amount corresponding to one pixel (i.e., one clock cycle period). The input binary image data I1 has already been processed into the binary form, and thus the value thereof is "0" or "1".
The mask forming portion 1 supplies the binary image data (which will be referred to as a "binary mask" hereafter) of the local image region shown in FIG. 76. For sake of description, following definition is given in connection with several terms.
(i) Reference Pixel: A central pixel on the lower row 24a in the binary mask 24. That is; the pixel at a position (i, j) on the screen in FIG. 76.
(ii) Reference Run R1: A run to which the reference pixel belongs.
(iii) Adjacent Run R2: A run adjacent to the reference run at (i-1)th row in the case where the reference pixel exists at an i-th row.
(iv) The upper row 24b in the binary mask 24 scans the reference run R2, and the lower row 24a scans the reference run R1. The binary mask 24 scans the binary image in accordance with the raster scan manner.
(v) Run Label: One label which is representative of labels added to the adjacent runs, and forms a provisional label of the reference run.
(vi) Concatenated Label: The newest label among labels in the adjacent runs existing before a -th column (in the raster scan) in the case where a plurality of adjacent runs exist.
The labeling circuit further includes a run label storage controller 6 which is responsive to the binary mask 24 from the mask forming portion 1 to detect a trailing end of the reference run R1, a run label storage 5 which stores the run label in response to a write signal generated upon detection of the trailing end of the reference run, a concatenated label storage 7 which detects a leading end of the adjacent run R2 and stores the current run label, and a temporary label determining portion 2 which is responsive to the binary mask 24, the stored contents of run label storage 5 and the stored contents of concatenated label storage 7 to determine the label of each pixel forming the adjacent run and assign the temporary label to each pixel.
The run label storage 5 has a memory structure of an FIFO (first-in first-out) type, and allows sequential read of the stored contents therefrom in the order of storage thereof. The run label storage 5 achieves following functions under control by the run label storage controller 6. The run label storage 5 is responsive to the binary mask 24 applied from the mask forming portion 1 to search the adjacent run R2 for storing one representative run label among run labels assigned to the adjacent run R2.
The concatenated label storage 7 resets its contents to 0 when both the adjacent run R2 and reference run R1 are interrupted in the binary mask 24 (i.e., in the case of P(i-1, j+1)=0, and P(i, j+1)=0).
The temporary label determining portion 2 includes a run label read controller 12 which is responsive to the binary mask 24 to detect the leading end of adjacent run R2 and applies a read instruction signal (read signal) to the run label storage 5 upon detection of the leading end, a temporary label selection controller 13 which inspects properness of the run label in response to the binary mask 24, run label supplied from the run label storage 5 and concatenated label supplied from the concatenated label storage 7, and produces a control signal for determining the temporary label of each pixel in the adjacent run in accordance with the result of inspection, and a new label counter 18 which produces and holds labels to be used when a new object appears.
The binary mask 24 further includes a temporary label selector 14 which is responsive to the control signal sent from the temporary label selection controller 13 to select one of the run label supplied from the run label storage 5, the concatenated label sent from the concatenated label storage 7 and the new label sent from the new label counter 18 as well as a temporary label register 15 which holds the output of temporary label selector 14.
The temporary label selection controller 13 increments by one the count of new label counter 18 when the count held thereby is selected as the temporary label by the temporary label selector 14. The contents of the temporary label register 15 are reset to "0" when the run label storage controller 6 detects the leading end of reference run R1 and detects the state where all the binary image data P(i-1, j-1), P(i-1, j) and P(i-1, j+1) on the upper row 24b of binary mask 24 are "0". The contents held in the temporary label register 15 are applied to the run label storage 5. The temporary label selector 14 applies the temporary label to the concatenated label storage 7. Thus, the concatenated label storage 7 is responsive to detection of the leading end of adjacent run R2 to latch as the concatenated label the label supplied from the temporary label selector 14.
The temporary label selection controller 13 feeds a select signal to the temporary label selector 14 upon detection of the leading end of adjacent run R2. This select signal is used for determining the temporary label for each pixel forming the adjacent run R2 in accordance with the concatenated label supplied from the concatenated label storage 7 and the run label applied from the run label storage 5. The temporary label selection controller 13 generates the select signal in accordance with the following temporary label determining logics.
(i) In the case of run label=0 and concatenated label=0: The contents of new label counter 18 are selected as the temporary label, and the count of new label counter 18 is incremented.
(ii) In the case of run label=0 and concatenated label.noteq.0: The concatenated label applied from the concatenated label storage 7 is selected as the temporary label.
(iii) In the case of run label.noteq.0 and concatenated label=0: The run label applied from the run label storage 5 is selected as the temporary label.
(iv) In the case of run label.noteq.0, concatenated label.noteq.0 and run label=concatenated label: Either the run label or concatenated label (e.g., run label) is selected as the temporary label.
(v) In the case of run label.noteq.0, concatenated label.noteq.0 and run label.noteq.concatenated label: Either the run label or concatenated label (e.g., concatenated label) is selected as the temporary label. In this case, both the concatenated label and run label are assigned to the same object, so that the concatenated label and run label are sent to an integration processing portion 4 via the integrated label feeding portion 3. The integration processing portion 4 produces a label correlation table in accordance with the concatenated label and run label.
The temporary label determining portion 2 further includes a temporary label feeding portion 16 and a temporary label feed controller 17. The temporary label feed controller 17 is responsive to the binary mask 24 to generate a select signal for selecting either the fixed value of "0" or the output of temporary label register 15 in accordance with the value of the adjacent reference pixel data P(i-1, j). The temporary label feeding portion 16 is responsive to the select signal sent from the temporary label feed controller 17 to select and feed either the fixed value "0" or the temporary label supplied from the temporary label register 15. The temporary label feed controller 17 controls the selecting operation of the temporary label feeding portion 16 in such a manner that the temporary label feeding portion 16 selects the temporary label supplied from the temporary label register 15 if the adjacent reference pixel data P(i-1, j) is 1 and selects the fixed value "0" if the adjacent reference pixel data P(i-1, j) is 0.
An operation of the labeling circuit shown in FIG. 77 will be described below with reference to FIGS. 78A-82C showing the steps in the labeling process and states of main components.
The reference run R1 is scanned with the lower row 24a of the binary mask 24 shown in FIG. 76, and the adjacent run R2 is scanned by the upper row 24b of the binary mask 24. It is assumed that the binary image data shown in FIG. 78A is to be processed. In FIG. 78A, "*" indicates portions of values are "1", and blank portions represents regions containing binary image data of which values are "0". "R11" and "R42" are names of runs which are used for sake of illustration.
The binary image to be processed has a size of N pixels in the horizontal direction (coordinate: j=1 to N-1) and M pixels in the vertical direction (coordinate: i=0 to M-1). Objects to be labeled are represented by "1" (portions bearing "*" shown in FIG. 78A) out of the binary values. Other portions are represented by the value of "0" (blank regions in FIG. 78A). Labels added to the runs start at the number of 1.
In the initial state shown in FIG. 78A, a following initial setting is conducted. The 1-bit line buffer 10 includes shift register stages for storing pixel data (binary image data) of one row, and the content of each register is set to 0. The count of new label counter 18 is initially set to 1. The stored contents of concatenated label storage 7 are set to 0, and the stored contents of temporary label register 15 are also set to 0. The run label storage 5 has cleared its stored contents and has not stored any label.
When the binary image data P(i, j+1) is supplied to the mask forming portion 1, the shift registers 11a-11f receive the binary image data P(i, j+1), P(i, j), P(i, j-1), P(i-1, j+1), P(i-1, j) and P(i-1, j-1), respectively, and will supply the received binary image data at the next clock cycle. Thereby, the binary mask 24 of two rows and three columns is produced.
As shown in FIG. 78, when the binary mask 24 scans the leading end of first reference run R11, the run label storage controller 6 confirms that all the binary image data on the upper row of binary mask 24 are 0, and resets the held value of the temporary label register 15 to 0. The binary image data P(0, 4) of the adjacent reference pixel (0, 4) is 0, so that the temporary label feeding portion 16 selects 0 and feeds the same therefrom.
As shown in FIG. 78C, when the binary mask 24 reaches the trailing end of reference run R11, the run label storage 5 stores the output of temporary label register 15. Since the adjacent run was not present on the 0th row, the held value of temporary label register 15 is kept at 0, i.e., the reset state, so that the run label storage 5 stores 0.
Even in the case where the binary mask 24 further shifts to scan the reference runs R12 and R13, the adjacent run is not present, so that an operation similar to that already executed for the reference run R11 is performed. Thus, when the lower row of binary mask 24 completes the scanning of the first row, the run label storage 5 stores three 0's as run labels of runs R11, R12 and R13. At this time, the count of new label counter 18 is 1, the held value of temporary label register 15 is 0, and the held value of concatenated label storage 7 is 0.
As shown in FIG. 79A, when the binary mask 24 scans the new rows (first and second rows) and detects the leading end of the first reference run R21, an operation is carried out similarly to the operation for the former row, so that the temporary label register 15 is reset.
As shown in FIG. 79B, in the course of rightward shift of the binary mask 24, the leading end of reference run R11 is detected. In response to detection of the leading end of reference run R11, the run label 0 added to the run R11 which has been stored in the run label storage 5 is read therefrom under the control of the run label storage controller 6.
At this time, since both the run label and concatenated label are 0, the temporary label selection controller 13 generates the control signal for selecting the count of 1, which is the output of new label counter 18, in accordance with the first condition. The temporary label selector 14 selects and outputs the count 1 of new label counter 18. At this time, the count of new label counter 18 is incremented by one under the control of the temporary label selection controller 13. The label 1 sent from the temporary label selector 14 is latched by the concatenated label storage 7 and temporary label register 15. Thereby, the temporary label for the adjacent run R11 is determined as 1.
As shown in FIG. 79C, when the binary mask 24 is further shifted rightward by one pixel, the binary image data P(1, 4) of the adjacent reference pixel (1, 4) goes to 1, so that the temporary label feeding portion 16 selects the label value 1, which is the output of temporary label register 15, and feeds the same therefrom. Hereafter, the temporary label feeding portion 16 selects and feeds therefrom the label value 1 as long as the binary image data of the pixel (adjacent reference pixel) of the central position on the upper row 24b of the binary mask 24 is 1.
As shown in FIG. 80A, when the reference pixel in the binary mask 24 reaches the pixel (2, 6), the pixels at the right ends of both the upper and lower rows in the binary mask 24 are data 0, so that the concatenated label storage 7 is reset.
As shown in FIG. 80B, when the binary mask 24 is further shifted rightward by one pixel, the trailing end of reference run R21 is detected. The run label storage 5 responds to detection of the trailing end of reference run R21 and stores the label value 1 supplied from the temporary label register 15. At this time, the run label storage 5 has stored two run labels of 0 for the runs R12 and R13 as well as the run label 1 for the run R21.
As shown in FIG. 80C, when the binary mask 24 reaches the leading ends of the reference run R22 and adjacent run R12, the label value 0 for the run R12 is first read from the run label storage 5. Since both the run label and concatenated label are 0, the temporary label selector 14 selects as the temporary label the count of 2 of the new label counter 18 in accordance with the first condition (i) for temporary label selection. The count of new label counter 18 is counted up to 3. The label 2 selected by the temporary label selector 14 is latched by the temporary label register 15 and concatenated label storage 7.
While the data of adjacent reference pixel in the binary mask 24 is 1, the temporary label feeding portion 16 selects as its output the label 2 sent from the temporary label register 15.
As shown in FIG. 81A, when the binary mask 24 reaches the trailing end of reference run R22, the run label storage 5 stores the temporary label value 2 supplied from the temporary label register 15. At this time, run label storage 5 stores the label value 0 for run R13, label value 1 for run R21 and label value 2 for run R22. Since both the pixels at the right ends of upper and lower rows in binary mask 24 are 0, the concatenated label storage 7 is reset, and the contents thereof go to 0.
Then, the binary mask 24 scans the reference run R23. The operation relating to this scan is the same as those carried out for the reference runs R11, R12 and R13. Thus, at the leading end of reference run R23, the temporary label register 15 and concatenated label storage 7 latch the data 0. As shown in FIG. 81B, when the binary mask 24 reaches the trailing end of reference run R23, the run label storage 5 stores the output data 0 of temporary label register 15. At this time, the run label storage 5 stores data of the run label 0 for the run R13, run label 1 for the run R21, run label 2 for the run R22 and run label 0 for the run R23. The concatenated label storage 7 has been reset to 0 since both the data values at the right ends of binary mask 24 went to 0.
When the binary mask 24 further shifts to detect the adjacent run R13, the run label 0 is read from the run label storage 5 similarly to the operation for the adjacent run R12. In accordance with the first condition (i) for temporary label selection, the temporary label selector 14 selects as the temporary label the count 3 which is the output of new label counter 18. The temporary label register 15 and concatenated label storage 7 latches this temporary label 3. The count of new label counter 18 is counted up by one to 4. The temporary label feeding portion 16 selects and outputs the temporary label 3 stored in the temporary label register 15. At the trailing end of reference run R24, the label value 3 supplied from the temporary label register 15 is stored as the run label in the run label storage 5.
When the binary mask 24 starts scanning of the next rows, i.e., second and third rows, the adjacent run R21 is first detected. In response to this, the run label 1 is read from the run label storage 5. The temporary label selector 14 selects the run label 1 sent from the run label storage 5 in accordance with the third condition (iii) for temporary label selection, and the temporary label register 15 and concatenated label storage 7 latch the value of 1. While the data of the adjacent reference pixel in binary mask 24 is 1, the temporary label feeding portion 16 selects and outputs the label value 1 as the temporary label.
Thereafter, the binary mask 24 detects the reference run R31. However, the reference run R31 is concatenated to the adjacent run R21, and the trailing end of adjacent run R21 is not yet detected. Therefore, the temporary label register 15, run label storage 5 and concatenated label storage 7 do not change its contents.
As shown in FIG. 81C, when the binary mask 24 reaches the leading end of adjacent run R22, the run label 2 for the adjacent run R22 is read from the run label storage 5. At this time, the reference run R31 exists, the output of concatenated label storage 7 is the label value 1, and thus the reference run and adjacent run which are concatenated together have different labels. In this case, the temporary label selector 14 selects a smaller label value (i.e., label value 1) in accordance with the fifth condition (v) for temporary label selection, and the temporary label register 15 and concatenated label storage 7 latch this label value 1. Since different labels are assigned to the same object, the integrated label feeding portion 3 supplies the label values 1 and 2 to the integration processing portion 4 under the control of the temporary label selection controller 13. The integration processing portion 4 stores the fact that the labels 1 and 2 are concatenated together.
While the binary mask 24 is scanning the adjacent run R22, the temporary label feeding portion 16 selects and outputs the label value 1 applied from the temporary label register 15 when the data of adjacent reference pixel is 1.
As shown in FIG. 82A, when the binary image data of reference pixel goes to P(3, 10), the pixels at the right ends of upper and lower rows in the binary mask 24 are 0, so that the concatenated label storage 7 is reset to 0. At the trailing end of reference run R31, the temporary label register 15 stores as the run label the label value supplied from the temporary label register 15.
As shown in FIG. 82B, when the binary mask 24 reaches the leading end of adjacent run R23, the run label 0 is read from the run label storage 5. Since the concatenated label storage 7 outputs the concatenated label of 0, data 4, i.e., output of the new label counter 18 is latched by the temporary label register 15 and run label storage 5 in accordance with the first condition (i) for temporary label selection. The count of new label counter 18 goes to 5.
For the adjacent run R23, the temporary label feeding portion 16 selects and outputs the label value 4 sent from the temporary label register 15. When reference runs R32 and R33 are scanned during scanning of the adjacent run R23, the label values 4, which are supplied from the temporary label register 15 at the respective trailing ends, are stored in the run label storage 5 as the run labels for the reference runs R32 and R33.
When the binary mask 24 scans adjacent runs R24 and R34, operations are carried out in the same manner as those for the adjacent run R13. When the scanning of the second and third rows is completed, the run label storage 5 has stored the run label 1 for run R31, run labels 4 for runs R32 and R33, and run label 3 for run R34.
While the binary mask 24 scans the adjacent runs R31 and R41 after starting the scanning of the next rows (third and fourth rows), the operation is carried out in the same manner as that which was carried out for the adjacent runs R21 (first run on the second row) and reference run R31 during the scanning of the row preceding the current row by one row.
As shown in FIG. 82C, when the binary mask 24 reaches the leading end of adjacent run R32, the run label 4 for the adjacent run R32 is read from the run label storage 5. At this time, the output of concatenated label storage 7 is 1. Therefore, there is established a relationship similar to that between the adjacent run R22 and reference run R31 (see FIG. 82A), so that different labels are assigned to the same object. At this time, the label of a smaller value (i.e., 1) is latched by the temporary label register 15 and concatenated label storage 7 in accordance with the fifth condition (v) for temporary label selection, and the integration processing portion 4 stores the fact that the labels 1 and 4 are concatenated together. For the adjacent run R32, the temporary label feeding portion 16 selects and outputs the label value 1 which is the output of temporary label register 15.
At the trailing end of R41, the run label storage 5 stores the run label 1. At this time, both the pixels at the right ends of upper and lower rows in binary mask 24 are 0, and the run is interrupted at these positions, so that the concatenated label storage 7 is reset to 0.
As shown in FIG. 83A, when the binary mask 24 reaches the leading end of adjacent run R33, the run label 4 for adjacent run R33 is read from the run label storage 5. Since the output of concatenated label storage 7 is 0, the temporary label selector 14 selects the run label 4 from the run label storage 5 in accordance with the third condition (iii) for temporary label selection, and the temporary label register 15 and concatenated label storage 7 latch the same. For the adjacent run R33, the temporary label feeding portion 16 outputs the label value 4 as the temporary label.
As shown in FIG. 83B, when the binary mask 24 reaches the leading end of adjacent run R34, the run label 3 for the adjacent run R34 is read from the run label storage 5. The output of concatenated label storage 7 is 4, and hence different labels are assigned to the same object. In this case, the concatenated label of a smaller label value (i.e., label value 3) between them is latched by the temporary label register 15 and concatenated label storage 7 in accordance with the fifth condition (v) for temporary label selection. Meanwhile, the integration processing portion 4 stores the fact that the labels 3 and 4 are concatenated together. For the adjacent run R34, the temporary label feeding portion 16 selects and outputs the label value 3, i.e., output of temporary label register 15. At the trailing end of reference run R42, the run label storage 5 stores the label value 3 which is the output of temporary label register 15.
When the binary mask 24 starts scanning of the next rows (fourth and fifth rows), adjacent runs, i.e., runs R41 and R42 are scanned. At the leading ends of adjacent runs R41 and R42, corresponding run labels 1 and 3 are read from the run label storage 5, respectively. The label value outputted from the concatenated label storage 7 is 0 at the time of detection of the run leading end, so that the run label supplied from the run label storage 5 is selected in accordance with the third condition (iii) for temporary label selection. For each of pixels belonging to the adjacent runs R41 and R42, the temporary label feeding portion 16 selects the outputs of temporary label register 15 and outputs, as the temporary labels, the run labels 1 and 3 of adjacent runs R41 and R42, respectively.
When all the scanning is completed, a temporary label image in which the temporary label is assigned to each pixel in the runs of binary image is obtained as shown in FIG. 83C. This temporary label image is stored in a temporary label memory (not shown), and in other words, the temporary label value corresponding to each pixel is stored in the temporary label memory.
The integration processing portion 4 has stored the fact of concatenation between the labels 1 and 2, between labels of 4 and 1, and between labels of 4 and 3. The integration processing portion 4, which analyzes the concatenation relationship among these labels, detects the fact that labels 2, 3 and 4 are diverged with the label 1 as a starting point, and rewrites these labels 2, 3 and 4 into the label 1. Thereby, a label image in which the same object bears a common label as shown in FIG. 84 is produced.
It is necessary to analyze the concatenation relationship between the temporary labels in order to obtain the label image shown in FIG. 84 by performing the integrating process for labels of the temporary label image shown in FIG. 83C. The analysis of the concatenation relationship between temporary labels is complicated, and is generally conducted with a software, so that the analysis requires a long time. It has been attempted to devise preparation of the concatenation table storing the concatenation relationship among labels for reducing a process time required for the analysis. As a method of preparing such a concatenation table (i.e., table storing a concatenation relationship among labels) is disclosed by Okuyama et al in "A High Speed Labeling Algorithm for Raster-Scanned Type", Japan Institute of Electronics Information Communication Engineers Transactions, Vol. J73-D-II, No. 1, January 1990, pp 36-45. This prior art method of preparing the concatenation table will be described below with reference to FIGS. 85A to 85D.
In an initial labeling state, as shown in FIG. 85A, the concatenation table contains data which are equal to values of addresses at which the data are stored. When it is found that different labels are added to one object (fifth condition (v) for temporary label selection), the different two labels are supplied to the integration processing portion 4 (the states shown in FIGS. 81C, 82C and 83B).
The integration processing portion 4 writes the label selected in accordance with the fifth condition for temporary label selection (i.e., label supplied to and latched by the temporary label register 15 and concatenated label storage 7) into the concatenation table using the other, i.e., unselected label as an address. More specifically, in the state shown in FIG. 81C, the concatenated label is 1 and the run label is 2, in which case the concatenated label is selected as the temporary label, so that the concatenated label 1 is written into the concatenation table using the run label 2 as an address, as shown in FIG. 85B.
Likewise, in the state shown in FIG. 82C, the concatenated label 1 is written as the write data into the concatenation table using the run label 4 as the address as shown in FIG. 85C. As shown in FIG. 85D, the run label 3 is selected as the temporary label in the state of FIG. 82B, so that the run label 3 is written as the write data into the concatenation table using the concatenated label 4 as the address.
Relabeling of the temporary label image is carried out using the concatenation table shown in FIG. 85D as a look-up table, so that a label image shown in FIG. 86 is obtained. More specifically, in the concatenation table shown in FIG. 85D, data in the concatenation table shown in FIG. 85D is read using each temporary label of the temporary label image as the address, and the processing is carried out for converting the temporary label in accordance with the data thus read. In this operation, the temporary label 4 is converted into the label 3 as shown in FIG. 85D, while the temporary label 3 maintains the label 3, so that two labels are assigned to the same object. In order to avoid this situation, the label image is scanned again to detect concatenation between pixels. If the concatenated pixels bear different labels, the concatenation table is converted again to carry out relabeling again for finally obtaining the label image shown in FIG. 84.
If the contents of concatenation table are rewritten by accessing several times the same address, so-called "label separation", i.e., assignment of different labels to the same object, occurs. For example, in FIGS. 85A to 85D, the address 4 in concatenation table was accessed two times, so that the contents thereof changed from 4 to 1, and then from 1 to 3. Therefore, the label 3 is separated from the label 1, and information that the run of label 3 is concatenated to the run of label 1 disappears, because the concatenation relationship information relating to the labels 4 and 1 disappears when storing the concatenation relationship between the labels 4 and 3. Thus, according to the manner of preparing the concatenation table in the prior art labeling method, the frequency of assignment of different labels to the same object is high, which results in increase of load in the label integrating process for analyzing the concatenation table and relabeling the temporary labels, and thus results in reduction of the processing performance.
Also in the relabeling process, it is necessary to inspect concatenation between pixels, so that the process is complicated. In other words, it is necessary to detect existence and nonexistence of separated label simultaneously with the relabeling operation, and to perform the relabeling again if the separated label is detected. In this case, it is necessary to access the concatenation table again for carrying out an operation such as rewrite of the contents. Such processing cannot be performed at a high speed. Further, a device of a large scale is required if a hardware is used to perform such complicated processing for detecting existence and nonexistence of the separated label during relabeling and for performing the relabeling based on result of detection. This also results in a disadvantage that the relabeling performance decreases as a whole.
When the concatenation table is analyzed, the label values which were 0, 1 and 3 go to successive values, or are converted into 0, 1 and 2, respectively, as shown in FIG. 85D. In this manner, there is finally prepared the conversion table which is a look-up table representing a relationship between the temporary labels and final labels. Using this conversion table, the temporary label image shown in FIG. 75 is scanned, and, using the conversion table thus prepared, the temporary label values are converted into the final label values to produce the final label image shown in FIG. 75.
In order to prepare the above conversion table, two tables, i.e., concatenation table and conversion table are required, and these tables require a large storage region, resulting in increase of the device scale.